/*
 * Copyright © 2017 eqxiu.com 北京中网易企秀科技有限公司  All rights reserved.
 */
package cn.hermit.core;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;

/**
 * IdentityOrderedMap which can support duplicated keys by order.
 * 
 * <p>It is implemented by linked list inside.</p>
 * 
 * @author Jack Gao (Chinese name : GAO JIANGUO, Email : linux.gjg@gmail.com)
 * @date 27 Jun, 2014
 */
public class IdentityOrderedMap<K, V> extends IdentityHashMap<K, V> {

	/**
	 * 
	 */
	private static final long serialVersionUID = -2223282646324365249L;

	/**
	 * The head of the doubly linked list.
	 */
	private transient Entry<K, V> header;

	/**
	 * The iteration ordering method for this linked hash map: <tt>true</tt> for
	 * access-order, <tt>false</tt> for insertion-order.
	 * 
	 * @serial
	 */
	private final boolean accessOrder;

	/**
	 * Constructs an empty insertion-ordered <tt>IdentityOrderedMap</tt>
	 * instance with the specified initial capacity and load factor.
	 * 
	 * @param initialCapacity
	 *            the initial capacity
	 * @param loadFactor
	 *            the load factor
	 * @throws IllegalArgumentException
	 *             if the initial capacity is negative or the load factor is
	 *             nonpositive
	 */
	public IdentityOrderedMap(int initialCapacity, float loadFactor) {
		super(initialCapacity, loadFactor);
		accessOrder = false;
	}

	/**
	 * Constructs an empty insertion-ordered <tt>IdentityOrderedMap</tt>
	 * instance with the specified initial capacity and a default load factor
	 * (0.75).
	 * 
	 * @param initialCapacity
	 *            the initial capacity
	 * @throws IllegalArgumentException
	 *             if the initial capacity is negative
	 */
	public IdentityOrderedMap(int initialCapacity) {
		super(initialCapacity);
		accessOrder = false;
	}

	/**
	 * Constructs an empty insertion-ordered <tt>IdentityOrderedMap</tt>
	 * instance with the default initial capacity (16) and load factor (0.75).
	 */
	public IdentityOrderedMap() {
		super();
		accessOrder = false;
	}

	/**
	 * Constructs an insertion-ordered <tt>IdentityOrderedMap</tt> instance with
	 * the same mappings as the specified map. The <tt>IdentityOrderedMap</tt>
	 * instance is created with a default load factor (0.75) and an initial
	 * capacity sufficient to hold the mappings in the specified map.
	 * 
	 * @param m
	 *            the map whose mappings are to be placed in this map
	 * @throws NullPointerException
	 *             if the specified map is null
	 */
	public IdentityOrderedMap(Map<? extends K, ? extends V> m) {
		super(m);
		accessOrder = false;
	}

	/**
	 * Constructs an empty <tt>IdentityOrderedMap</tt> instance with the
	 * specified initial capacity, load factor and ordering mode.
	 * 
	 * @param initialCapacity
	 *            the initial capacity
	 * @param loadFactor
	 *            the load factor
	 * @param accessOrder
	 *            the ordering mode - <tt>true</tt> for access-order,
	 *            <tt>false</tt> for insertion-order
	 * @throws IllegalArgumentException
	 *             if the initial capacity is negative or the load factor is
	 *             nonpositive
	 */
	public IdentityOrderedMap(int initialCapacity, float loadFactor,
			boolean accessOrder) {
		super(initialCapacity, loadFactor);
		this.accessOrder = accessOrder;
	}

	/**
	 * Called by superclass constructors and pseudoconstructors (clone,
	 * readObject) before any entries are inserted into the map. Initializes the
	 * chain.
	 */
	@Override
	void init() {
		header = new Entry<K, V>(-1, null, null, null);
		header.before = header.after = header;
	}

	/**
	 * Transfers all entries to new table array. This method is called by
	 * superclass resize. It is overridden for performance, as it is faster to
	 * iterate using our linked list.
	 */
	@Override
	void transfer(IdentityHashMap.Entry<K, V>[] newTable, boolean rehash) {
		int newCapacity = newTable.length;
		for (Entry<K, V> e = header.after; e != header; e = e.after) {
			if (rehash)
				e.hash = (e.key == null) ? 0 : hash(e.key);
			int index = indexFor(e.hash, newCapacity);
			e.next = newTable[index];
			newTable[index] = e;
		}
	}

	/**
	 * Returns <tt>true</tt> if this map maps one or more keys to the specified
	 * value.
	 * 
	 * @param value
	 *            value whose presence in this map is to be tested
	 * @return <tt>true</tt> if this map maps one or more keys to the specified
	 *         value
	 */
	public boolean containsValue(Object value) {
		// Overridden to take advantage of faster iterator
		if (value == null) {
			for (Entry<K, V> e = header.after; e != header; e = e.after)
				if (e.value == null)
					return true;
		} else {
			for (Entry<K, V> e = header.after; e != header; e = e.after)
				if (value.equals(e.value))
					return true;
		}
		return false;
	}

	/**
	 * Returns the value to which the specified key is mapped, or {@code null}
	 * if this map contains no mapping for the key.
	 * 
	 * <p>
	 * More formally, if this map contains a mapping from a key {@code k} to a
	 * value {@code v} such that {@code (key==null ? k==null :
	 * key.equals(k))}, then this method returns {@code v}; otherwise it returns
	 * {@code null}. (There can be at most one such mapping.)
	 * 
	 * <p>
	 * A return value of {@code null} does not <i>necessarily</i> indicate that
	 * the map contains no mapping for the key; it's also possible that the map
	 * explicitly maps the key to {@code null}. The {@link #containsKey
	 * containsKey} operation may be used to distinguish these two cases.
	 */
	public V get(Object key) {
		Entry<K, V> e = (Entry<K, V>) getEntry(key);
		if (e == null)
			return null;
		e.recordAccess(this);
		return e.value;
	}

	/**
	 * Removes all of the mappings from this map. The map will be empty after
	 * this call returns.
	 */
	public void clear() {
		super.clear();
		header.before = header.after = header;
	}

	/**
	 * IdentityOrderedMap entry.
	 */
	private static class Entry<K, V> extends IdentityHashMap.Entry<K, V> {
		// These fields comprise the doubly linked list used for iteration.
		Entry<K, V> before, after;

		Entry(int hash, K key, V value, IdentityHashMap.Entry<K, V> next) {
			super(hash, key, value, next);
		}

		/**
		 * Removes this entry from the linked list.
		 */
		private void remove() {
			before.after = after;
			after.before = before;
		}

		/**
		 * Inserts this entry before the specified existing entry in the list.
		 */
		private void addBefore(Entry<K, V> existingEntry) {
			after = existingEntry;
			before = existingEntry.before;
			before.after = this;
			after.before = this;
		}

		/**
		 * This method is invoked by the superclass whenever the value of a
		 * pre-existing entry is read by Map.get or modified by Map.setHeader. If the
		 * enclosing Map is access-ordered, it moves the entry to the end of the
		 * list; otherwise, it does nothing.
		 */
		void recordAccess(IdentityHashMap<K, V> m) {
			IdentityOrderedMap<K, V> lm = (IdentityOrderedMap<K, V>) m;
			if (lm.accessOrder) {
				lm.modCount++;
				remove();
				addBefore(lm.header);
			}
		}

		void recordRemoval(IdentityHashMap<K, V> m) {
			remove();
		}
	}

	private abstract class LinkedHashIterator<T> implements Iterator<T> {
		Entry<K, V> nextEntry = header.after;
		Entry<K, V> lastReturned = null;

		/**
		 * The modCount value that the iterator believes that the backing List
		 * should have. If this expectation is violated, the iterator has
		 * detected concurrent modification.
		 */
		int expectedModCount = modCount;

		public boolean hasNext() {
			return nextEntry != header;
		}

		public void remove() {
			if (lastReturned == null)
				throw new IllegalStateException();
			if (modCount != expectedModCount)
				throw new ConcurrentModificationException();

			IdentityOrderedMap.this.remove(lastReturned.key);
			lastReturned = null;
			expectedModCount = modCount;
		}

		Entry<K, V> nextEntry() {
			if (modCount != expectedModCount)
				throw new ConcurrentModificationException();
			if (nextEntry == header)
				throw new NoSuchElementException();

			Entry<K, V> e = lastReturned = nextEntry;
			nextEntry = e.after;
			return e;
		}
	}

	private class KeyIterator extends LinkedHashIterator<K> {
		public K next() {
			return nextEntry().getKey();
		}
	}

	private class ValueIterator extends LinkedHashIterator<V> {
		public V next() {
			return nextEntry().value;
		}
	}

	private class EntryIterator extends LinkedHashIterator<Map.Entry<K, V>> {
		public Map.Entry<K, V> next() {
			return nextEntry();
		}
	}

	// These Overrides alter the behavior of superclass view iterator() methods
	Iterator<K> newKeyIterator() {
		return new KeyIterator();
	}

	Iterator<V> newValueIterator() {
		return new ValueIterator();
	}

	Iterator<Map.Entry<K, V>> newEntryIterator() {
		return new EntryIterator();
	}

	/**
	 * This override alters behavior of superclass put method. It causes newly
	 * allocated entry to get inserted at the end of the linked list and removes
	 * the eldest entry if appropriate.
	 */
	void addEntry(int hash, K key, V value, int bucketIndex) {
		super.addEntry(hash, key, value, bucketIndex);

		// Remove eldest entry if instructed
		Entry<K, V> eldest = header.after;
		if (removeEldestEntry(eldest)) {
			removeEntryForKey(eldest.key);
		}
	}

	/**
	 * This override differs from addEntry in that it doesn't resize the table
	 * or remove the eldest entry.
	 */
	void createEntry(int hash, K key, V value, int bucketIndex) {
		IdentityHashMap.Entry<K, V> old = table[bucketIndex];
		Entry<K, V> e = new Entry<K, V>(hash, key, value, old);
		table[bucketIndex] = e;
		e.addBefore(header);
		size++;
	}

	/**
	 * Returns <tt>true</tt> if this map should remove its eldest entry. This
	 * method is invoked by <tt>put</tt> and <tt>putAll</tt> after inserting a
	 * new entry into the map. It provides the implementor with the opportunity
	 * to remove the eldest entry each time a new one is added. This is useful
	 * if the map represents a cache: it allows the map to reduce memory
	 * consumption by deleting stale entries.
	 * 
	 * <p>
	 * Sample use: this override will allow the map to grow up to 100 entries
	 * and then delete the eldest entry each time a new entry is added,
	 * maintaining a steady state of 100 entries.
	 * 
	 * <pre>
	 * private static final int MAX_ENTRIES = 100;
	 * 
	 * protected boolean removeEldestEntry(Map.Entry eldest) {
	 * 	return size() &gt; MAX_ENTRIES;
	 * }
	 * </pre>
	 * 
	 * <p>
	 * This method typically does not modify the map in any way, instead
	 * allowing the map to modify itself as directed by its return value. It
	 * <i>is</i> permitted for this method to modify the map directly, but if it
	 * does so, it <i>must</i> return <tt>false</tt> (indicating that the map
	 * should not attempt any further modification). The effects of returning
	 * <tt>true</tt> after modifying the map from within this method are
	 * unspecified.
	 * 
	 * <p>
	 * This implementation merely returns <tt>false</tt> (so that this map acts
	 * like a normal map - the eldest element is never removed).
	 * 
	 * @param eldest
	 *            The least recently inserted entry in the map, or if this is an
	 *            access-ordered map, the least recently accessed entry. This is
	 *            the entry that will be removed it this method returns
	 *            <tt>true</tt>. If the map was empty prior to the <tt>put</tt>
	 *            or <tt>putAll</tt> invocation resulting in this invocation,
	 *            this will be the entry that was just inserted; in other words,
	 *            if the map contains a single entry, the eldest entry is also
	 *            the newest.
	 * @return <tt>true</tt> if the eldest entry should be removed from the map;
	 *         <tt>false</tt> if it should be retained.
	 */
	protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
		return false;
	}

}